Many languages, including most programming languages, are context-free languages. These languages have properties that lend themselves to efficient computational methods such as determining if a string of characters is a valid string in the context-free language. These methods are most typically performed by context-free language compilers which read a string, determine if the string is valid for a given context-free language, determine the implicit structure conveyed by the string, and perform one or more actions as a result of the determined structure. As is the case with most practical systems, however, complexity bears down on the task of developing context-free language compilers.
Even simple context-free languages may describe an infinite number of valid strings and confuse even experienced computer scientists. For context-free languages described by complex grammars, the number of production rules can easily number in the hundreds or thousands. As with any human-engineered system, especially those coping with massive complexity, extensive testing is necessary to ensure proper operational behavior. Because compilers for programming languages are used to generate object code for a great variety of applications, including those for which the safety of humans is at stake, it is even more critical that they be tested as thoroughly and accurately as possible.